package demo.practice.bfs;

import java.util.*;

public class P1926 {
    /**
     * [
     * ["+",".","+","+","+","+","+"],
     * ["+",".","+",".",".",".","+"],
     * ["+",".","+",".","+",".","+"],
     * ["+",".",".",".",".",".","+"],
     * ["+","+","+","+",".","+","."]
     * ]
     *
     * [0,1]
     * @param args
     */

    public static void main(String[] args) {
        P1926 p1926 = new P1926();
        int i = p1926.nearestExit(new char[][]{{'.'}, {'.'}},
                new int[]{1, 0});
        System.out.println(i);
    }

    public int nearestExit(char[][] maze, int[] entrance) {
        if (maze == null || maze.length == 0) {
            return -1;
        }
        int h = maze.length;
        int w = maze[0].length;
        boolean[][] visited = new boolean[h][w];
        if (entrance[0] < 0 || entrance[0] >= h || entrance[1] < 0 || entrance[1] >= w) {
            return -1;
        }
        //起点就是砖头
        if (maze[entrance[0]][entrance[1]] == '+') {
            return -1;
        }

        Queue<int[]> q = new LinkedList<>();
        q.add(entrance);


        visited[entrance[0]][entrance[1]] = true;
        maze[entrance[0]][entrance[1]] = '+';
        int step = 0;
        List<int[]> direction = Arrays.asList(new int[]{1, 0}, new int[]{0, 1}, new int[]{-1, 0}, new int[]{0, -1});
        while (!q.isEmpty()) {
            int size = q.size();
            while (size > 0) {
                int[] pop = q.poll();
                if (step > 0 && (pop[0] == 0 || pop[1] == 0 || pop[0] == h - 1 || pop[1] == w - 1)) {

                    return step;
                }
                for (int[] d : direction) {
                    int x = d[0] + pop[0];
                    int y = d[1] + pop[1];
                    if (  x >= 0 && x < h && y >= 0 && y < w &&  maze[x][y] == '.' &&!visited[x][y] ){
                        q.add(new int[]{x, y});
                        visited[x][y]=true;
                        //maze[x][y] = '+';
                    }
                }
                size--;
            }
            step++;
        }
        return -1;
    }
}
